/*
day58
2019.10.25
*/
#include<stdlib.h>
struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

void help(struct TreeNode *root,int sum[])
{
	if(!root) return ;
	help(root->right,sum);
	
	root->val += sum[0];
	sum[0] = root->val;
	
	help(root->left,sum);
}


struct TreeNode* convertBST(struct TreeNode* root){
	
	if(!root) return NULL;
	int sum[1];
	sum[0]=0;
	help(root,sum);
	
	return root;
}


class Solution {
public:
	int sum=0;
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return NULL;
		convertBST(root->right);
		
		root->val += sum;
		sum = root->val;
		
		convertBST(root->left);
		
		return root;
    }
};


int main()
{
	return 0;
}
